package leetcode_day._2022._202210._2131;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 1235. 规划兼职工作
 * 算法：序列 DP + 二分查找
 * 定义 dp[i], 表示前 i 个工作中的最大报酬
 * 1、第 i 个工作不加入
 * 2、第 i 个工作加入
 * 3、第 i 个工作加入, 并且加在第 j(j < i) 个工作后面
 *
 * @author yezh
 * @version 1.0
 * @date 2022/10/22 23:02
 */
public class _22_1235 {

    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        List<int[]> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) list.add(new int[]{startTime[i], endTime[i], profit[i]});
        Collections.sort(list, (a, b) -> a[1] - b[1]);
        int[] dp = new int[n + 10];
        for (int i = 1; i <= n; i++) {
            int[] info = list.get(i - 1);
            int a = info[0], b = info[1], c = info[2];
            dp[i] = Math.max(dp[i - 1], c);
            int l = 0, r = i - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                // 找到从后往前最接近 i 的工作
                if (list.get(mid)[1] <= a) l = mid;
                else r = mid - 1;
            }
            if (list.get(l)[1] <= a) dp[i] = Math.max(dp[i], dp[l + 1] + c);
        }
        return dp[n];
    }

}
